package 动态规划.可dp可二分;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/10 19:53
 */
public class 安排邮筒的再思考 {

    /*
    做一些 basecase 的优化
    总体的 思路还是原来的思路
     */
    public int solution(int nums[],int k){
        // 需要 对数组 进行一个 排序!
        Arrays.sort(nums);

        int len = nums.length;
        /*
         *L。。。。R minDistance[l][r] 表示的是 在 l----r 之间 只有 一个 邮筒安排的 时候
         * 的最小 距离和
         */
        int minDistance [][] = new int [len + 1][len + 1];
        for(int L = 0;L < len;L++ ){
            // 因 为 R >= L (这是 距离) 因为 只有一个  坐标 那么 最小距离  就是 0
            for(int R = L + 1;R < len;R++){
                // 这段代码 非常的巧妙的 , 这个 思想就非常的巧妙 !
                minDistance[L][R] = minDistance[L][R - 1] + nums[R] - nums[L + R >> 1];
            }
        }


        return recursion(0,k,minDistance,len);
    }
    /*
      这样的递归 代码看起来
      就非常的清晰了，而且很简洁
     */
    private int recursion(int index, int k, int[][] minDistance, int  len) {
        // 如果剩余 的 用户的 数量 <= k 邮局的数量 ,那直接 每家都安装一个邮局 ,最距离和最小为 0;
        // 不写 这个代码 也可以, 但是 会走很多,多余的 递归层数
        if(len - index <= k)
            return 0;
        if( k == 1)
            return minDistance[index][len - 1];
        // 这个 也 很经典 MAX 会溢出, 那选择一半试一下!
        int ans = Integer.MAX_VALUE >> 1;
        for(int scale = 1;index + scale <= len - 1;scale++){
            ans = Math.min(ans,minDistance[index][index + scale - 1] + recursion(index + scale,k - 1,minDistance,len));
        }
        return ans;
    }

}
